# 作者: 家里蹲 吴越洋
# 2023年03月02日18时56分03秒
import random
import time
class Sort():
    def __init__(self,len):
        self.len=len
        self.arr=[]
        self.arr_random()

    def arr_random(self):
        for i in range(0,self.len):
            self.arr.append(random.randint(1,99))

    def count_sort(self):
        max_data=max(self.arr)
        arr=[0]*(max_data+1)
        for i in self.arr:
            arr[i]+=1
        j=0
        for i in range(0,max_data+1):
            if arr[i]>0:
                for k in range(0,arr[i]):
                    self.arr[j]=i
                    j+=1

    def heap_adjust(self,adjust,len):
        arr=self.arr
        dad=adjust
        son=dad*2+1 #左孩子
        while son<len:
            if son+1<len and arr[son+1]>arr[son]:
                son+=1

            if arr[son]>arr[dad]:
                arr[son],arr[dad]=arr[dad],arr[son]
                dad=son
                son=2*dad+1
            else:
                break

    def heap_sort(self):
        arr = self.arr
        # 调整堆变为一个大根堆
        for i in range(self.len // 2 - 1, -1, -1):
            self.heap_adjust(i, self.len)
        arr[0], arr[self.len - 1] = arr[self.len - 1], arr[0]
        for len in range(self.len-1,1,-1):
            self.heap_adjust(0,len)
            arr[0], arr[len - 1] = arr[len - 1], arr[0]

if __name__ == '__main__':
    head_time=time.time()
    sort=Sort(100000)
    # print(sort.arr)
    # print('\n')
    sort.count_sort()
    print(time.time() - head_time)
    head_time=time.time()
    sort=Sort(100000)
    sort.heap_sort()
    print(time.time() - head_time)